// https://www.lintcode.com/problem/spiral-matrix/description?_from=ladder&&fromId=6

class Solution {
public:
    /**
     * @param matrix: a matrix of m x n elements
     * @return: an integer list
     */
    
    // WA，以后不要总想这样解了
    // void traverse(vector<vector<int>> matrix, vector<int>& result, int pos_x, int pos_y)
    // {
    //     if ((pos_x > int(matrix.size() - 1 - pos_x)) || (pos_y > int(matrix[0].size() - 1 - pos_y)))
    //     {
    //         return;
    //     }
    //     for (int k = pos_y; k < matrix[0].size() - pos_y; ++k)
    //     {
    //         result.push_back(matrix[pos_x][k]);
    //     }
    //     for (int k = pos_x + 1; k < matrix.size() - pos_x; ++k)
    //     {
    //         result.push_back(matrix[k][matrix[0].size() - 1 - pos_y]);
    //     }
    //     for (int k = matrix[0].size() - pos_y - 2; k >= pos_y; --k)
    //     {
    //         result.push_back(matrix[matrix.size() - 1 - pos_x][k]);
    //     }
    //     for (int k = matrix.size() - pos_x - 2; k > pos_x; --k)
    //     {
    //         result.push_back(matrix[k][pos_y]);
    //     }
    //     traverse(matrix, result, pos_x + 1, pos_y + 1);
    // }
    
    // vector<int> spiralOrder(vector<vector<int>> &matrix) {
    //     vector<int> result;
    //     if (matrix.empty()) return result;
    //     traverse(matrix, result, 0, 0);
    //     return result;
    // }
    
private:
    int step[4][2];
    vector<int> ret;
    bool canUse[100][100];
    
public:
    /**
     * @param matrix a matrix of m x n elements
     * @return an integer array
     * step 记录上下左右四个方向
     */
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // Write your code here
        step[0][0] = 0;
        step[0][1] = 1;
        step[1][0] = 1;
        step[1][1] = 0;
        step[2][0] = 0;
        step[2][1] = -1;
        step[3][0] = -1;
        step[3][1] = 0;
        ret.clear();
        memset(canUse, true, sizeof(canUse));
        dfs(matrix, 0, 0, -1);
        
        return ret;
    }

    //通过step的方向变换实现螺旋
    void dfs(vector<vector<int>> &matrix, int direct, int x, int y)
    {
        for(int i = 0; i < 4; i++)
        {
            int j = (direct + i) % 4;
            int tx = x + step[j][0];
            int ty = y + step[j][1];
            if (0 <= tx && tx < matrix.size() && 0 <= ty && ty < matrix[0].size() && canUse[tx][ty])
            {
                canUse[tx][ty] = false;
                ret.push_back(matrix[tx][ty]);                
                dfs(matrix, j, tx, ty);               
            }            
        }
    }
};